﻿//#include <iostream>
//#include <vector>
//using namespace std;

//动态规划练习

//粉刷房子
//https://leetcode.cn/problems/JEj789/submissions/627976790/
//class Solution
//{
//public:
//    int minCost(vector<vector<int>>& costs)
//    {
//        int n = costs.size();
//        vector<vector<int>> dp(n + 1, vector<int>(3));
//
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
//            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
//            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
//        }
//
//        int ret = min(dp[n][0], min(dp[n][1], dp[n][2]));
//
//        return ret;
//    }
//};


//买卖股票的最佳时机（含冷冻期）
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/submissions/628000919/
//class Solution
//{
//public:
//    int maxProfit(vector<int>& p)
//    {
//        int n = p.size();
//        vector<vector<int>> dp(n + 1, vector<int>(3));
//        dp[0][0] = -p[0];
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i - 1]);
//            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
//            dp[i][2] = dp[i - 1][0] + p[i - 1];
//        }
//
//        return max(dp[n][1], dp[n][2]);
//    }
//};

//买卖股票的最佳时机(含手续费)
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
//class Solution
//{
//public:
//    int maxProfit(vector<int>& p, int fee)
//    {
//        int n = p.size();
//        vector<vector<int>> dp(n + 1, vector<int>(2));
//
//        dp[0][0] = -p[0];
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i - 1]);
//            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + p[i] - fee);
//        }
//
//        return dp[n][1];
//    }
//};

//买卖股票的最佳时机3
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
//class Solution
//{
//public:
//    int maxProfit(vector<int>& p)
//    {
//        int n = p.size();
//        vector<vector<int>> f(n + 1, vector<int>(3));
//        f[0][1] = -0x3f3f3f3f;
//        f[0][2] = -0x3f3f3f3f;
//        auto g = f;
//
//        f[0][0] = -p[0];
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 0; j <= 2; j++)
//            {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i - 1]);
//                g[i][j] = g[i - 1][j];
//                if(j >= 1)
//                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + p[i - 1]);
//            }
//        }
//
//        return max(g[n][0], max(g[n][1], g[n][2]));
//    }
//};


//买卖股票的最佳时机4
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
//class Solution
//{
//public:
//    int maxProfit(int k, vector<int>& p)
//    {
//        int n = p.size();
//        //k = min(k, n / 2);
//        //该题需要在创建dp表时进行部分初始化
//        vector<vector<int>> f(n + 1, vector<int>(k + 1, -0x3f3f3f3f));
//        auto g = f;
//        f[0][0] = -p[0];
//        g[0][0] = 0;
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 0; j <= k; j++)
//            {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i - 1]);
//                g[i][j] = g[i - 1][j];
//                if (j >= 1)
//                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + p[i - 1]);
//            }
//        }
//
//        int ret = 0;
//        for (int i = 0; i < g[n].size(); i++)
//        {
//            ret = max(ret, g[n][i]);
//        }
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v1({ 1,2,4,2,5,7,2,4,9,0 });
//   cout <<  s.maxProfit(4, v1) << endl;
//
//    return 0;
//}


//最大子数组和
//https://leetcode.cn/problems/maximum-subarray/submissions/628047080/
//class Solution
//{
//public:
//    int maxSubArray(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        for (int i = 1; i <= n; i++)
//        {
//            dp[i] = max(nums[i-1], dp[i - 1] + nums[i-1]);
//        }
//        int ret = -INT_MAX;
//        for (int i = 1; i <= n; i++)
//        {
//            ret = max(ret, dp[i]);
//        }
//
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v1({ -2,1,-3,4,-1,2,1,-5,4 });
//    cout << s.maxSubArray(v1) << endl;
//  
//    vector<int> v2({ 5,4,-1,7,8 });
//    cout << s.maxSubArray(v2) << endl;
//
//    return 0;
//}


//环形子数组的最大和
//https://leetcode.cn/problems/maximum-sum-circular-subarray/
//class Solution
//{
//public:
//    int maxSubarraySumCircular(vector<int>& nums)
//    {
//        int n = nums.size();
//        int sum = 0;
//        for (int i = 0; i < n; i++)
//        {
//            sum += nums[i];
//        }
//
//        vector<int> f(n + 1);
//        auto g = f;
//        f[0] = 0;
//        g[0] = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            f[i] = max(nums[i], nums[i - 1] + f[i - 1]);
//            g[i] = min(nums[i], nums[i - 1] + g[i - 1]);
//        }
//
//        int fmax = -INT_MAX;
//        int gmin = INT_MAX;
//
//        for (int i = 1; i <= n; i++)
//        {
//            fmax = max(fmax, f[i]);
//            gmin = min(gmin, g[i]);
//        }
//
//        if (sum == gmin)
//            return fmax;
//        else
//            return max(fmax, sum - gmin);
//    }
//};



//typedef long long LL;
//
//const int N = 55, M = 15;
//
//const LL INF = 0x3f3f3f3f3f3f3f3f;
//
//int n, k, d;
//LL arr[N];
//LL f[N][M], g[N][M];
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//	cin >> k >> d;
//	// 初始化放在填表中进⾏了
//	for (int i = 1; i <= n; i++) // 填写每⼀⾏
//	{
//		g[i][1] = f[i][1] = arr[i];
//		for (int j = 2; j <= min(i, k); j++) // 挑选⼏个⼈
//		{
//			f[i][j] = -INF; // 初始化
//			g[i][j] = INF; // 初始化
//			for (int prev = max(i - d, j - 1); prev <= i - 1; prev++) // 前⾯挑选的最后⼀个位置
//			{
//			f[i][j] = max(max(f[prev][j - 1] * arr[i], g[prev][j - 1] *
//			arr[i]), f[i][j]);
//			g[i][j] = min(min(f[prev][j - 1] * arr[i], g[prev][j - 1] *
//			arr[i]), g[i][j]);
//			}
//		}
//	}
//	LL ret = -INF;
//	for (int i = k; i <= n; i++) ret = max(ret, f[i][k]);
//	cout << ret << endl;
//	return 0;
//}


//跳台阶扩展问题
//https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee?tpId=230&tqId=39750&ru=/exam/oj
//#include <iostream>
//using namespace std;
//
//int n;
//int dp[25];
//
//int main()
//{
//	cin >> n;
//	dp[0] = 1;
//
//	for (int i = 1; i < n; i++)
//	{
//		dp[i] = dp[i - 1] * 2;
//	}
//
//	cout << dp[n-1] << endl;
//
//	return 0;
//}


//包含不超过两种字符的最长子串
//https://www.nowcoder.com/practice/90d6a362fa7d4c519d557da797bb02ce?tpId=196&tqId=40552&ru=/exam/oj
//#include <iostream>
//#include <unordered_map>
//
//using namespace std;
//
//int main()
//{
//	unordered_map<char, int> hash1;
//	string str;
//	cin >> str;
//	int n = str.size();
//
//	int right = 0, left = 0;
//	int ret = 0;
//	while (right < n)
//	{
//		hash1[str[right]]++;
//		while (hash1.size() > 2)
//		{
//			char ch = str[left];
//			if (hash1[str[left]] == 1)
//			{
//				hash1.erase(ch);
//				left++;
//				break;
//			}
//			hash1[str[left]]--;
//			left++;
//		}
//
//		ret = max(ret, right + 1 - left);
//		right++;
//	}
//
//	cout << ret << endl;
//	return 0;
//}


//int main()
//{
//	unordered_map<char, int> hash1;
//	hash1['a']++;
//	hash1['a']++;
//	hash1['b']++;
//	hash1['b']++;
//	hash1['b']++;
//
//	cout << hash1['a'] << endl;
//	cout << hash1.size() << endl;
//
	//hash1['b']--;
//	hash1.erase('b');
//
//	cout << hash1.size() << endl;
//	cout << hash1['b'] << endl;
//
//
//	//cout << hash1.count('a') << endl;
//
//	return 0;
//}

//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//class Solution
//{
//    string s;
//    bool st[26] = { 0 };
//    vector<string> vs;
//public:
//    vector<string> Permutation(string str)
//    {
//        int n = str.size();
//        dfs(1, n, str);
//    }
//
//    void dfs(int pos, int n, string str)
//    {
//        if (pos > n)
//        {
//            vs.push_back(s);
//            return;
//        }
//
//        for (int i = 0; i < n; i++)
//        {
//            if (st[str[i] - 'a'])  continue;
//            s += str[i];
//            st[str[i] - 'a'] = 1;
//            dfs(pos + 1, n, str);
//            st[str[i] - 'a'] = 0;
//        }
//    }
//};



